题目大意
求两个已经排好序的数列的中位数
解题思路
下面两个方法也适用于查找第k大的数
方法一
https://www.cnblogs.com/TenosDoIt/p/3554479.html
复杂度为O（k）的算法，在归并两个数组的过程中，如果如果已经选择的元素达到k（或中位数），就不需要再归并下去了。
方法二
转自：http://www.cnblogs.com/zuoyuan/p/3759682.html
首先我们来看如何找到两个数列的第k小个数，即程序中getKth(A, B , k)函数的实现。
用一个例子来说明这个问题：
A = {1，3，5，7}
B = {2，4，6，8，9，10}；
如果要求第7个小的数，A数列的元素个数为4，B数列的元素个数为6；
k/2 = 7/2 = 3，而A中的第3个数A[2]=5；B中的第3个数B[2]=6；
A[2]小于B[2]；则A[0]，A[1]，A[2]中必然不可能有第7个小的数。
因为A[2]小于B[2]，所以比A[2]小的数最多可能为A[0], A[1], B[0], B[1]这四个数，也就是说A[2]最多可能是第5个大的数，由于我们要求的是getKth(A, B, 7)；现在就变成了求getKth(A’, B, 4)；
即A’ = {7}，因为A[0]，A[1]，A[2]中没有解，所以我们直接删掉它们就可以了。
B不变，求这两个数列的第4个小的数，这个可以使用递归来实现。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| class Solution(object):
def getKth(self, A, B, k):
lenA = len(A)
lenB = len(B)
if lenA > lenB: # 保证A比B短
return self.getKth(B, A, k)
if lenA == 0: # A已为空，直接返回B中间数
return B[k - 1]
if k == 1: # 如果找的是第一个，直接返回两个数组比较小的那个
return min(A[0], B[0])
pa = min(k/2, lenA)
print 'pa:', pa, 'pb', k-pa
pb = k - pa
print 'A[pa - 1]', A[pa - 1], 'B[pb - 1]',B[pb - 1]
# 索引为pa和pb，所以是A[pa - 1] 和 B[pb - 1]
if A[pa - 1] <= B[pb - 1]:
return self.getKth(A[pa:], B, pb)
else:
return self.getKth(A, B[pb:], pa)
def findMedianSortedArrays(self, A, B):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
lenA = len(A)
lenB = len(B)
if (lenA + lenB) % 2 == 1:
return self.getKth(A, B, (lenA + lenB)/2 + 1)
else:
return (self.getKth(A, B, (lenA + lenB)/2) + self.getKth(A, B, (lenA + lenB)/2 + 1)) * 0.5
|
总结
分治法